//
// Created by 下次一定 on 2021/9/23.
//

/*
给你一个包含 n 个整数的数组nums，判断nums中是否存在三个元素 a，b，c ，
 使得a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
链接：https://leetcode-cn.com/problems/3sum
 * */

#include <iostream>
#include <algorithm>

using namespace std;

vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> ans;
    if(nums.size()<3) return ans;
    sort(nums.begin(), nums.end());
    if(nums[0]>0) return ans;
    int i = 0;
    while(i<nums.size()){
        if(nums[i]>0) break;        // 1楼网友指正，将这个if语句放这里提前终止循环
        int left = i+1, right = nums.size()-1;
        while(left< right){

            // 转换为long long避免加法过程中溢出
            int  y = nums[i];
            int x = nums[left];
            int z = nums[right];
            if(x + y >0-z)
                right--;
            else if(x + y <0-z)
                left++;
            else{
                ans.push_back({nums[i], nums[left], nums[right]});
                // 相同的left和right不应该再次出现，因此跳过
                while(left<right&&nums[left]==nums[left+1])
                    left++;
                while(left<right&&nums[right] == nums[right-1])
                    right--;
                left++;
                right--;
            }
        }
        // 避免nums[i]作为第一个数重复出现
        while(i+1<nums.size()&&nums[i] == nums[i+1])
            i++;
        i++;
    }
    return ans;
}

int main(){

}
